﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Vux.Helper.Numeric
{
    /// <summary>
    /// Lớp tính toán số lớn, cơ số 256
    /// </summary>
    public class BigUInt
    {
        private byte[, ,] CongRa;
        private byte[, ,] CongNho;

        private byte[, ,] TruRa;
        private byte[, ,] TruNo;

        private int @base;

        #region Generate Otomat Table
        private void GenOtomatTable()
        {
            // var s = 2;  // Chỉ có thể nhớ hoặc nợ ở 2 trạng thái: 0 hoặc 1
            CongRa = new byte[@base, @base, 2];
            CongNho = new byte[@base, @base, 2];
            TruRa = new byte[@base, @base, 2];
            TruNo = new byte[@base, @base, 2];
            // Generate Cong, Tru Otomat Table
            for (int a = 0; a < @base; a++)
            {
                for (int b = 0; b < @base; b++)
                {
                    for (int s = 0; s < 2; s++)
                    {
                        var Temp1 = a + b + s;
                        CongRa[a, b, s] = (byte)(Temp1 % @base); // := (a + b + s) % 256;
                        // CongNho[a, b, s] = (byte)((a + b + s) / @base);
                        if (Temp1 >= @base)
                        {
                            CongNho[a, b, s] = 1;
                        }

                        var Temp2 = a - s; // Accumulate
                        TruRa[a, b, s] = (byte)((Temp2 - b + @base) % @base); // := (a - b - s) % 256;
                        if (Temp2 < b)
                            TruNo[a, b, s] = 1;
                    }
                }
            }
        }
        #endregion

        #region Constructors
        /// <summary>
        /// Default base 256
        /// </summary>
        /// <returns></returns>
        public static BigUInt Create()
        {
            return Create(256);
        }

        public static BigUInt Create(int @base)
        {
            if (@base > 256)
                throw new ArgumentException("Base must be less than or equals to 256");
            var byteCalculator = new BigUInt();
            byteCalculator.@base = @base;
            byteCalculator.GenOtomatTable();
            #region Test 1
            //Console.Clear();
            //Console.WriteLine("Cong");
            //for (int a = 0; a < @base; a++)
            //{
            //    for (int b = 0; b < @base; b++)
            //    {
            //        // Cong Ra
            //        for (int s = 0; s < 2; s++)
            //        {
            //            Console.WriteLine("Cong Ra({0}, {1}, {2}) = {3}, Nho = {4}", a, b, s, byteCalculator.CongRa[a, b, s], byteCalculator.CongNho[a, b, s]);
            //        }
            //    }
            //}
            ////
            //Console.WriteLine("Tru");
            //for (int a = 0; a < @base; a++)
            //{
            //    for (int b = 0; b < @base; b++)
            //    {
            //        // Tru Ra
            //        for (int s = 0; s < 2; s++)
            //        {
            //            Console.WriteLine("Tru Ra({0}, {1}, {2}) = {3}, No = {4}", a, b, s, byteCalculator.TruRa[a, b, s], byteCalculator.TruNo[a, b, s]);
            //        }
            //    }
            //}

            #endregion

            return byteCalculator;
        }

        private BigUInt()
        {
        }

        public byte[] Cong(byte[] a, byte[] b)
        {
            var s = (byte)0;
            var lena = a.Length;
            var lenb = b.Length;

            var k = lena > lenb ? lena : lenb;
            var c = new byte[k];

            if (lena > lenb)
            {
                Array.Resize(ref b, lena);
            }
            else if (lenb > lena)
            {
                Array.Resize(ref a, lenb);
            }
            for (int i = 0; i < k; i++)
            {
                c[i] = CongRa[a[i], b[i], s];
                s = CongNho[a[i], b[i], s];
            }
            if (s > 0)
            {
                Array.Resize(ref c, k + 1);
                c[k] = s;
            }
            return c;
        }

        public byte[] Tru(byte[] a, byte[] b)
        {
            // Giai thuat giong phep cong
            // return Cong(a, b);

            var s = (byte)0;
            var lena = a.Length;
            var lenb = b.Length;
            var k = lena > lenb ? lena : lenb;
            var c = new byte[k];

            if (lena > lenb)
            {
                Array.Resize(ref b, lena);
            }
            else if (lenb > lena)
            {
                Array.Resize(ref a, lenb);
            }
            for (int i = 0; i < k; i++)
            {
                c[i] = TruRa[a[i], b[i], s];
                s = TruNo[a[i], b[i], s];
            }
            if (s > 0)
            {
                Array.Resize(ref c, k + 1);
                c[k] = s;
            }
            return c;
        }
        /// <summary>
        /// Phien ban chua Min
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public byte[] Nhan(byte[] a, byte[] b)
        {
            var lena = a.GetLength(0);
            var lenb = b.GetLength(0);
            var lenc = lena + lenb + 2;
            var c = new byte[lenc];
            var i = 0;
            for (int j = 0; j < lenb; j++)
            {
                if (b[j] > 0)
                {
                    var ci0 = c.GetBytes(0, i);
                    var ci1 = c.GetBytes(i);
                    var temp = a.Mutiply(b[j]);
                    var ci = Cong(temp, ci1); // cong a * b[j] voi ci tu vi tri i

                    ByteHelper.Concat(ref ci0, ci); // Noi lai doan tach
                    c = ci0;
                }
                // Tang i, chi so cua c
                i++;
            }
            return c;
        }

        public int Chia(byte[] a, byte[] b)
        {
            var quotient = 0;
            var sobichia = a.Trim();
            var sochia = b.Trim();

            while (sobichia.Compare(sochia) >= 0)
            {
                // increase quotient by Tru();
                quotient++;
                sobichia = Tru(sobichia, sochia).Trim();
            }
            return quotient;
        }

        public byte[] Chia(byte[] a, byte[] b, out byte[] remain)
        {
            var sobichia = a.Trim();
            var sochia = b.Trim();

            var dividable = sobichia.Compare(sochia);

            if (dividable <= 0)
            {
                if (dividable == 0)
                {
                    remain = new byte[] { 0 };
                    return new byte[] { 1 };
                }
                else // dividable = -1
                {
                    remain = sobichia.Clone() as byte[];
                    return new byte[] { 0 };
                }
            }
            // else
            var lena = sobichia.Length;
            var lenb = sochia.Length;
            var lenr = lenb;
            var n = lena - lenr;
            var r = sobichia.GetBytes(n);  // Lấy lenr bytes cao của mảng a;

            if (r.Compare(sochia) < 0)
            {
                lenr += 1;
                n = lena - lenr;
                r = sobichia.GetBytes(n);
            }

            var lenq = 1;
            var quot = Chia(r, sochia);
            var quotient = new byte[1] { (byte)quot };
            var prod = sochia.Mutiply(quot);
            var re = Tru(r, prod).Trim();

            for (var i = n - 1; i >= 0; i--)
            {
                r = new byte[] { sobichia[i] };
                ByteHelper.Concat(ref r, re);

                quot = Chia(r, sochia);
                Array.Resize(ref quotient, lenq + 1);
                quotient[lenq++] = (byte)quot; // mod 256

                prod = sochia.Mutiply(quot);
                re = Tru(r, prod).Trim();
            }
            remain = re;
            Array.Reverse(quotient);
            return quotient;
        }

        #endregion

        #region Extesion Methods
        public byte[] GetFactorial(int ip_int_value)
        {
            if (ip_int_value > 1)
                return GetFactorial(ip_int_value - 1).Mutiply(ip_int_value);
            else
                return new byte[1] { 1 };
        }

        #endregion

        public void TestMethod()
        {
            // BigInteger in .NET 4.0

            //var fac = GetFactorial(256);
            //var big = new BigInteger(14545454545454554555);
            //var a = big / 100;

        }
    }
}
